package leetcode.editor.cn;

//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//
//
//
//
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,3,4,5]
//输出：[5,4,3,2,1]
//
//
// 示例 2：
//
//
//输入：head = [1,2]
//输出：[2,1]
//
//
// 示例 3：
//
//
//输入：head = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 链表中节点的数目范围是 [0, 5000]
// -5000 <= Node.val <= 5000
//
//
//
//
// 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
//
// Related Topics 递归 链表 👍 2921 👎 0

import java.util.List;

class ReverseLinkedList {
    public static void main(String[] args) {

        Solution solution = new ReverseLinkedList().new Solution();
        ListNode head = new ListNode(-1);
        ListNode pre = head;
        new ListNode(-1);
        for (int i = 1; i < 6; i++) {
            ListNode node = new ListNode(i);
            pre.next = node;
            pre = pre.next;
        }
        ListNode head1 = solution.reverseList(head.next);

    }

//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode newhead = new ListNode(-1);//新建头节点
            while (head != null) {
                ListNode node = head;//新建指针指向老的第一个节点
                head = head.next;   //先让head指向下一个节点，保存最新的头节点
                node.next = newhead.next;//在新链表表上头插法
                newhead.next = node;
            }
            return newhead.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
